package Algorithm.dynamicProgramming.knapsackDp;

/**
 * 416. 分割等和子集 https://leetcode.cn/problems/partition-equal-subset-sum
 * 题目简述：给你一个只包含正整数的非空数组，判断是否能将其划分为和相等的两部分。
 */
public class CanPartition {

    /**
     * 思路一：01背包-最大价值问题，设数组总和的一半为w，将集合中的元素视为重量和价值相等的物品，那么问题就转化为了容量为w的背包能放入物品最大价值总和是否为w（不可能超过w），
     *       如果不是则说明无法凑出和为w的子集，若可以则能凑出和为w的子集，而剩余元素肯定也为和为w的子集
     */
    public boolean canPartition(int[] nums) {
        if(nums.length < 2) return false;
        int sum = 0;
        for(int num : nums)
            sum += num;
        if(sum%2 != 0) return false;
        int w = sum/2;
        int[] dp = new int[sum/2 + 1];
        for(int i=0;i < nums.length;i++) {
            for(int j=w;j >= nums[i];j--) {
                dp[j] = Math.max(dp[j], dp[j-nums[i]] + nums[i]);
            }
        }
        return dp[w] == w;
    }





    /**
     * 思路二：回溯算法 划分k相等的子集
     */
}
